package main

import (
	"../util"
	"fmt"
)

func main() {
	root := &util.TreeNode{
		Val:  1,
		Left: nil,
		Right: &util.TreeNode{
			Val: 2,
			Left: &util.TreeNode{
				Val:   3,
				Left:  nil,
				Right: nil,
			},
			Right: nil,
		},
	}
	r := preorderTraversal(root)
	fmt.Println(r)
}

func preorderTraversal(root *util.TreeNode) []int {
	result := make([]int, 0)
	stack := make([]*util.TreeNode, 0)
	if root != nil {
		stack = append(stack, root)
		for len(stack) > 0 {
			top := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			result = append(result, top.Val)
			if top.Right != nil {
				stack = append(stack, top.Right)
			}
			if top.Left != nil {
				stack = append(stack, top.Left)
			}
		}
	}

	return result
}
